#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* createList(int arr[], int n) {
    if (n == 0) {
        return nullptr;
    }

    ListNode* head = new ListNode(arr[0]);
    ListNode* cur = head;
    for (int i = 1; i < n; i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }

    return head;
}

void printList(ListNode* head) {
    if (head == nullptr) {
        cout << "null" << endl;
    }

    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) {
            cout << "->";
        }
        head = head->next;
    }

    cout << endl;
}

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;

        // null    1    2
        //  pre   cur

        // null    1    2   null
        //             pre   cur
        while (cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
};

int main() {
    int arr[] = {1, 2, 3};
    ListNode* head = createList(arr, 3);

    printList(head);
    printList(Solution().reverseList(head));
    return 0;
}